package org.dlsu.mt.parser;

import java.util.Enumeration;
import java.util.Stack;
import java.util.Vector;

import org.dlsu.mt.parser.generator.ParseTable;
import org.dlsu.mt.parser.generator.ParseTableEntry;

/**
 * The GLRParserEngine is a GLR parser engine that given the lexical analyzer and a parse table, parses a given string.
 * The engine handles multiple entries in the LR parsing table by saving the current configuration and first evaluating
 * one of the possible entries and later backtracking to evaluate the remaining ones. This parser engine also handles when
 * the token passed can be interpretted in more than one way. In this case, when it encounters that a token can have to
 * possible interpretation then it saves the current configuration, continues to evaluate the token with one of the possible
 * interpretations and later backtracking and evaluating it with the other interpretation. When the parse() method is called
 * the engine parses the string and returns a list or a Vector of accepted derivation trees or C-Structure, represented by
 * the Node class.
 */
public class GLRParserEngine implements ParserEngineInterface {

	private static final int STARTSTATE= 0; // The default start state

	private ParseTable parseTable; // The parse table to use
	private Stack stack = new Stack(); // The symbol stack used for parsing
	private Stack stackTemp, stackPOS;
	private LexerInterface lex; // The lexical analyzer used
	private LexerInterface lexTemp,lexPOS;

	private Vector possibleEntries; // The vector or list of possible parse trees
	private Stack configStack = new Stack(); //Stack containing the different configurations of the system
	private Stack configStack2 = new Stack();
	private SemanticStack semanticStack = new SemanticStack(); //Stack used to store the nodes or C-Structure
	private SemanticStack semanticTemp, semanticPOS;


	private ParseTableEntry currentEntry;

	private Integer currentState; // Stores top of stack symbol (s)
	private Word wordA, wordATemp, wordAPOS; // Stores the next token from input (a)


	/**
	 * Creates a new parser engine provided the table and the tokens to be parsed
	 *
	 * @param p The parse table
	 * @param lex The tokens to be parsed
	 */
	public GLRParserEngine(ParseTable p, LexerInterface lex){
		this.parseTable = p;
		this.lex = lex;
	}

	/**
	 * Creates a new parser engine provided the table
	 * LexerInterface has to be set to be able to use it
	 *
	 * @param p The parse table
	 */
	public GLRParserEngine(ParseTable p){
		this.parseTable = p;
		this.lex = null;
	}

	/**
	 * Creates a new parser engine
	 * The LexerInterface and ParseTable has to be set to be able to use it
	 */
	public GLRParserEngine() {
		this.parseTable= null;
		this.lex= null;
	}

	/**
	 * Resets the parser engine
	 */
	public void reset() {
		stack.clear();
		stackTemp = null;
		stackPOS = null;
		lex = null;
		lexTemp = null;
		lexPOS = null;
		possibleEntries = null;
		configStack.clear();
		configStack2.clear();
		semanticStack.clear();
		semanticTemp = null;
		semanticPOS = null;
	}

	/**
	 * Sets the lexer interface to use
	 *
	 * @param lex The set of tokens or lexical units
	 */
	public void setLexer(LexerInterface lex) {
		this.lex = lex;
	}

	/**
	 * Sets the parse table to use
	 *
	 * @param pt The parse table to use
	 */
	public void setParseTable(ParseTable pt) {
		this.parseTable = pt;
	}

	/**
	 * Starts the parsing process and returns the list of accepted parse trees
	 *
	 * @return The list or vector of accepted parse trees
	 */
	public Vector parse() throws Exception{

		Vector parseTrees = new Vector();
		int tagIndex =0;
		Enumeration posTags; // stores possible POS Tags

		if (lex == null)
			throw new RuntimeException("Cannot parse without a lexer set");
		if (parseTable == null)
			throw new RuntimeException("Cannot parse without a parse table set");

		// Push Initial State
		stack.push(new Integer(STARTSTATE));

		// Points to the symbol in ip (a)
		wordA = lex.nextToken();
		posTags = wordA.getPOSTags();
		
		

		while (posTags.hasMoreElements())
		{
			Word tmp = (Word)wordA.clone();
			tmp.setPOSTag((String)posTags.nextElement());
			
//System.out.println(tmp.getWholeWord()+" as "+tmp.getCurrentPOSTag());

			
			configStack.push(tmp);
			configStack.push(lex.clone());
			configStack.push(stack.clone());
			configStack.push(semanticStack.clone());
		}


		do
		{


				if (!configStack.isEmpty()) {
					semanticStack = (SemanticStack) configStack.pop();
					stack = (Stack)configStack.pop();
					lex = (LexerInterface) configStack.pop();
					wordA = (Word) configStack.pop();
				}

				currentState = (Integer)stack.peek();

				possibleEntries = parseTable.getEntry( currentState.intValue(), wordA.getCurrentPOSTag());

				configStack.size();
	// lexTemp, stackTemp, semanticTemp and wordATemp contains
	//     the original state/configuration of the engine
				lexTemp = (LexerInterface) lex.clone();
				stackTemp = (Stack) stack.clone();
				semanticTemp = (SemanticStack) semanticStack.clone();
				wordATemp = (Word) wordA.clone();



				for ( int i=0; i< possibleEntries.size(); i++)
				{
					
					currentEntry = (ParseTableEntry) possibleEntries.elementAt(i);
					if(currentEntry.getAction().equalsIgnoreCase("Shift")){

						stack.push(wordA);
						semanticStack.push(wordA);

						// Push s'
						stack.push(new Integer(currentEntry.getState()));

						//Advance the ip to the next symbol
						wordA = lex.nextToken();

						// Save the stack configuration


						posTags = wordA.getPOSTags();

						while (posTags.hasMoreElements())
						{
							Word tmp = (Word)wordA.clone();
							tmp.setPOSTag((String)posTags.nextElement());
							configStack.push(tmp);
							configStack.push(lex.clone());
							configStack.push(stack.clone());
							configStack.push(semanticStack.clone());
						}

					}
					else if(currentEntry.getAction().equalsIgnoreCase("Reduce")){


						for( int j=0; j<2*currentEntry.getRuleSize(); j++)
							stack.pop();

						// get s'
						int tempnum = ((Integer)stack.peek()).intValue();

						// Get goto[s', A]
						Vector v = parseTable.getEntry(tempnum, currentEntry.getRuleLHS());
						ParseTableEntry x =(ParseTableEntry) v.elementAt(0);

						// check if goto is valid
						if (!x.getAction().equalsIgnoreCase("error"))
						{
							// Push A
							stack.push(currentEntry.getRuleLHS());
							// Push goto[s', A]
							stack.push(new Integer(x.getState()));

							Node node = new Node(currentEntry.getRuleLHS(), currentEntry.getRule());

							Stack temp = new Stack();

							for( int j=0; j<currentEntry.getRuleSize(); j++)
							{
								temp.push(semanticStack.pop());
							}

							while(!temp.empty())
							{
								node.addChild((Symbol)temp.pop());
							}

							semanticStack.push(node);

							// Save the stack configuration
							Word tmp = (Word)wordA.clone();
							configStack.push(tmp);
							configStack.push(lex.clone());
							configStack.push(stack.clone());
							configStack.push(semanticStack.clone());
						}

					}
					else if(currentEntry.getAction().equalsIgnoreCase("Accept")){
						Node node = (Node)semanticStack.pop();
						parseTrees.addElement(node);
					}
					else {
					}

					if (i+1 != possibleEntries.size()) {
						wordA = (Word) wordATemp.clone();
						lex = (LexerInterface) lexTemp.clone();
						stack = (Stack) stackTemp.clone();
						semanticStack = (SemanticStack) semanticTemp.clone();
					}
				}


		}while( !configStack.isEmpty());

		return parseTrees;
	}
}